package com.kabuda.hot100.链表.easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author kabuda
 * @Description
 * @create 2025-02-18 14:09
 * 给你一个单链表的头节点 head ，请你判断该链表是否为
 * 回文链表
 * 。如果是，返回 true ；否则，返回 false 。
 * 输入：head = [1,2,2,1]
 * 输出：true
 */
public class t234_回文链表 {

    public static void main(String[] args) {
        ListNode headNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(2);
        ListNode listNode4 = new ListNode(1);
        headNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        System.out.println(isPalindrome1(headNode));
    }


    /**
     * 集合反转比较
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        Integer[] array = list.toArray(new Integer[0]);
        Collections.reverse(list);
        Integer[] array2 = list.toArray(new Integer[0]);

        return Arrays.equals(array2, array);
    }

    /**
     * 双指针比较
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome1(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp.val);
            temp = temp.next;
        }
        int back = list.size() - 1;
        int front = 0;
        while (front < back) {
            if (list.get(front) != list.get(back)) {
                return false;
            }
            back--;
            front++;
        }
        return true;
    }

}


